- Time limit: 1.00 s
- Memory limit: 512 MB
A game has planets, connected by teleporters. Two planets and belong to the same kingdom exactly when there is a route both from to and from to . Your task is to determine for each planet its kingdom.
Input
The first input line has two integers and : the number of planets and teleporters. The planets are numbered .
After this, there are lines describing the teleporters. Each line has two integers and : you can travel from planet to planet through a teleporter.
Output
First print an integer : the number of kingdoms. After this, print for each planet a kingdom label between and . You can print any valid solution.
Constraints
Example
Input:
5 6 1 2 2 3 3 1 3 4 4 5 5 4
Output:
2 1 1 1 2 2